package com.sh.stack;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 * @ClassName MidToPolandNotation
 * @Description TODO
 * @Author yaoqiang
 * @Date 2020/11/6 14:37
 * @Version 1.0
 */
public class MidToPolandNotation {
    public static void main(String[] args) {
        /**
         * 中缀转后缀
         * 思路：
         *  1、   1+((2+3)*4)-5转成1 2 3 + 4 * + 5 -
         *  2、因直接对str操作不方便，先将1+((2+3)*4)-5的中缀表达式对应的list
         *      即1+((2+3)*4)-5=》ArrayList[1, +, (, (, 2, +, 3, ), *, 4, ), -, 5]
         *  3、将得到的中缀表达式对应的list=》转成后缀表达式对应的list
         *  ArrayList[1, +, (, (, 2, +, 3, ), *, 4, ), -, 5]=>[1, 2, 3, +, 4, *, +, 5, -]
         */

        String expression="1+((2+3)*4)-5";
        List<String> infix=  toInfixExpression(expression);
        System.out.println( infix);
        List<String> suffix=parseSuffixExpressionList(infix);
        System.out.println(suffix);
    }

    /**
     * 将中缀表达式转成对应的list
     * @param expression
     * @return
     */
    public  static List<String> toInfixExpression(String expression){
        List<String> list=new ArrayList<String>();//定义一个list存转后的结果
        int i=0;//定义一个指针，用于遍历中缀表达式的字符串
        String str;//对多位数的拼接
        char c;//每遍历一个一个就放到c中
        do {
            //如果c是一个数字，加入到ls
            if ((c=expression.charAt(i))<48 || (c=expression.charAt(i))>57){
                list.add(""+c);
                i++;
            }else {
                //考虑到多位数
                str="";
                while (i<expression.length()&&(c=expression.charAt(i))>=48&&(c=expression.charAt(i))<=57){
                    str+=c;
                    i++;
                }
                list.add(""+str);
            }
        }while (i< expression.length());
        return list;
    }

    public  static List<String> parseSuffixExpressionList(List<String> list){
        //定义两个栈
        Stack<String> s1=new Stack<>();
        //因为s2在整个过程中没有pop,直接使用list<String>//用于存储中间结果的list
        List<String> s2=new ArrayList<>();
        //遍历list
        for (String item:list){
            //如果是一个数，加入s2
            if (item.matches("\\d+")){
                s2.add(item);
            }else if(item.equals("(")){//左括号
                s1.push(item);
            }else if(item.equals(")")){
                //如果是右括号，则依次弹出s1栈顶的运算符，并压入s2,直到遇到左括号停止，此时将这一对括号丢弃
                while (!s1.peek().equals("(")){
                    s2.add(s1.pop());
                }
                s1.pop();//将左括号弹出消除

            }else {
                //当item的优先级小于等于栈顶，将s1的栈顶运算符弹出并压入到s2中，再次循环

                while (s1.size()>0 && Operation.getValue(item)<=Operation.getValue(s1.peek())){
                    s2.add(s1.pop());
                }
                //将item压入栈
                s1.push(item);
            }
        }

        //将s1中加入到s2中的
        while (s1.size()!=0){
            s2.add(s1.pop());
        }
        return s2;//list是有序的，不需要逆序

    }



}

/**
 * 定义一个类，可以返回一个运算符对应的优先级
 */
class Operation{
    private static int ADD=1;
    private static int SUB=1;
    private static int MUL=2;
    private static int DIV=2;

    public static int getValue(String oper){
        int result=0;
        switch (oper){
            case "+":result=ADD; break;
            case "-":result=SUB; break;
            case "*":result=MUL; break;
            case "/":result=DIV; break;
            default:break;
        }
        return result;
    }


}